#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int data;
    struct node * next;
}Node,*NodePtr;

#if 0
// 1 2 3 0
// 尾插法，在尾节点插入，每插入一个节点，即成尾节点。
Node * createList()
{
    Node * head = (Node *)malloc(sizeof (Node));
    if(NULL == head)
        exit(-1);
    head -> next = NULL;

    Node *t = head, * cur;
    int nodeData;
    scanf("%d",&nodeData);
    while (nodeData) {
        cur = (Node *)malloc(sizeof (Node));
        if(NULL == head)
            exit(-1);
        cur -> data = nodeData;
        t ->next = cur;
        t = cur;
        scanf("%d",&nodeData);
    }
    t -> next = NULL;
    return head;
}


// 头插法，就是在头节点后面插入元素，每插入一个元素，即为首节点。
// *head 头节点 首节点 .... 尾节点
// 1. 让新来的节点先有所指向，避免打断原有的指向。
//cur -> data = nodeData;
//cur ->next = head -> next;

Node * createList()
{
    Node * head = (Node *)malloc(sizeof (Node));
    if(NULL == head)
        exit(-1);
    head -> next = NULL;
    int nodeData;
    Node *cur;
    scanf("%d",&nodeData);
    while (nodeData) {
        cur = (Node *)malloc(sizeof (Node));
        if(NULL == head)
            exit(-1);
        cur -> data = nodeData;
        cur ->next = head -> next;
        head -> next = cur;
        scanf("%d",&nodeData);
    }
    return head;
}
#endif

// 真正意义上的创建链表，就是创建一个空链表。
Node * createList()
{
    Node * head = (Node *)malloc(sizeof (Node));
    if(NULL == head)
        exit(-1);
    head -> next = NULL;
    return head;
}

// 插入操作 本质就是头插法
void insertList(Node *head,int nodeData)
{
    Node * cur = (Node *)malloc(sizeof (Node));
    if(NULL == head)
        exit(-1);
    cur -> data = nodeData;
    cur ->next = head -> next;
    head -> next = cur;
}


void traverseList(Node *head)
{
    head = head -> next;
    while (head) {
        printf("%d\n",head -> data);
        head = head -> next;
    }
}

// 求长
// 本质是遍历
int lenList(Node *head)
{
    int len = 0;
    head = head->next;
    while (head) {
        len++;
        head = head->next;
    }
    return len;
}

// 查
// 返回查找的节点的地址
Node *searchList(Node *head,int findData)
{
    head = head->next;
    while (head) {
        if(head->data == findData)
            break;
        head = head->next;
    }
    return head;
}
// 删
//void deleteNodeOfList(Node *head,Node *pfind)
//{
//    while (head->next != pfind) {
//        head = head ->next;
//    }
//    head->next = pfind->next;
//    free(pfind);
//    pfind = NULL;
//}
// 删 优化
void deleteNodeOfList(Node *head,Node *pfind)
{
    if(pfind->next == NULL)
    {
        while (head->next != pfind) {
            head = head ->next;
        }
        head->next = pfind->next;
        free(pfind);
        pfind = NULL;
    }
    else {
        Node *t = pfind->next;
        pfind->data = pfind->next->data;
        pfind->next = pfind->next->next;
        free(t);

    }
}
# if 0
// 冒泡排序
void popSortList(Node *head)
{
    int len = lenList(head);
    head = head -> next;
    Node *p,*q;
    for(int i = 0; i < len - 1; i++)
    {
        p = head; // 每次内层循环从 head 开始
        q = p->next;  // q 总是指向 p 的下一个节点，也就是被比较的节点
        for(int j = 0; j < len - 1 -i; j++)
        {
            if(p -> data > q->data)
            {
                p->data ^= q->data;
                q->data ^= p->data;
                p->data ^= q->data;
            }
            p = p -> next;
            q = p -> next;
        }
    }
}
#endif

// 冒泡排序优化
void popSortList(Node *head)
{
    int len = lenList(head);
    Node *prep,*q,*p,*t;
    for(int i = 0; i < len - 1; i++)
    {
        prep = head;
        p = head -> next;
        q = p -> next;
        for(int j = 0; j < len - 1 - i; j++)
        {
            if(p -> data > q -> data)
            {
                prep -> next = q;
                p -> next = q -> next;
                q -> next =p;
                t = p;
                p = q;
                q = t;
            }
            prep = prep -> next;
            p = p -> next;
            q = p -> next;
        }
    }
}

// 逆序
void reverseList(Node *head)
{
    Node *cur = head -> next;
    head -> next = NULL;

    Node *t;
    while (cur) {
        t = cur;
        cur = cur -> next;

        t->next = head -> next;
        head -> next = t;

    }
}

// 销毁
// 有多少 malloc 就有多少 free
void destroyList(Node * head)
{
    Node *t;
    while (head) {
        t = head;
        head = head -> next;
        free(t);
    }
}

int main()
{
    Node *head = createList();
    srand(time(NULL));
    for(int i = 0; i< 10; i++)
    {
//        insertList(head,i);
        insertList(head,rand()%100);
    }
    traverseList(head);
    printf("len of list = %d\n",lenList(head));
    Node *pfind = searchList(head,0);
//    Node *pfind = searchList(head,9);
    if(pfind == NULL)
    {
        printf("find none\n");
    }
    else {
        // 改
        pfind->data = 1000;
        traverseList(head);
        // 删
        printf("your find in list\n");
        deleteNodeOfList(head,pfind);

    }
    traverseList(head);
    popSortList(head);
    printf("after popsort\n");
    traverseList(head);
    printf("after reverse\n");
    reverseList(head);
    traverseList(head);

    destroyList(head);
    return 0;
}
